#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
	int lengthOfLIS(vector<int>& nums)
	{
		vector<int> ends { nums[0] };
		for (int i = 1, len = nums.size(); i < len; i++) {
			int num = nums[i];
			int idx = binary_search(ends, num);
			if (idx > 0 && ends[idx - 1] == num) continue;
			if (idx == ends.size())	ends.emplace_back(num);
			else					ends[idx] = num;
		}

		return ends.size();
	}

private:
	int binary_search(vector<int>& nums, int target)
	{
		int lo = 0, hi = nums.size();
		while (lo < hi) {
			int mid = lo + (hi - lo >> 1);
			(target < nums[mid]) ? hi = mid : lo = mid + 1;
		}
		return lo;
	}
};

int main()
{
	Solution solution;
	return 0;
}
